package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/longest-common-subsequence/
 * @create 2025/8/29 10:23
 * @since JDK17
 */

public class Solution18 {
    static int[][]dp = new int[1001][1001];

    public int f(char s1[], char s2[], int len1, int len2) {
        if (len1 == 0 || len2 == 0) {
            return 0;
        }
        if (dp[len1][len2] != -1) {
            return dp[len1][len2];
        }
        int ans = 0;
        if (s1[len1 - 1] == s2[len2 - 1]) {
            ans = 1 + f(s1, s2, len1 - 1, len2 - 1);
        } else {
            ans = Math.max(f(s1, s2, len1 - 1, len2), f(s1, s2, len1, len2 - 1));
        }
        return dp[len1][len2] = ans;
    }



    public int longestCommonSubsequence(String text1, String text2) {
        char[] s1 = text1.toCharArray(), s2 = text2.toCharArray();
//        for (int i = 0; i <= s1.length; i++) {
//            Arrays.fill(dp, 0, s2.length + 1, -1);
//        }
//        return f(s1, s2, s1.length, s2.length);
        return f2(s1, s2);
    }

    public int f2(char[] s1, char[] s2) {
        int n = s1.length, m = s2.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }
}
